The SIM not supported error usually occurs when the device is locked to a carrier other than the one for the SIM you have inserted. If a device was hacked to unlock it, a restore will indeed revert the device back to the original carrier locked status it was originally sold as.
Did you buy this device new and originally activated with AT&T? If not, did you get it officially unlocked by whichever carrier it was originally locked to?
If you bought it used and have never restored before, I would say your device was sold with a hack installed to act as if it was unlocked, and the restore you executed has reverted it back to the locked status it originally had. Assuming it was originally sold in the USA, that would be T-Mobile as the only other possible GSM carrier (as a Sprint or Verizon iPhone 4s would never have worked on AT&T's network).